package algorithm;

public class T00148 {
    public static void main(String[] args) {
        int[] arr = {4,2,1,3};
        ListNode sentinel = new ListNode(-1);
        ListNode cur = sentinel;
        for (int i = 0; i < arr.length; i++) {
             cur.next = new ListNode(arr[i]);
             cur = cur.next;
        }

        cur = sentinel.next;
        System.out.println("排序前：");
        while (cur != null) {
            System.out.printf("%d\t", cur.val);
            cur = cur.next;
        }
        ListNode newHead = new Solution().sortList(sentinel.next);

        cur = newHead;
        System.out.println("排序后：");
        while (cur != null) {
            System.out.printf("%d\t", cur.val);
            cur = cur.next;
        }
    }

    static class Solution {
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) return head;
            ListNode p1 = head, p2 = head;
            while (p2.next.next != null) {
                p1 = p1.next;
                p2 = p2.next;
                if (p2.next.next != null) p2 = p2.next;
            }
            p2 = p1.next;
            p1.next = null;
            ListNode h1 = sortList(head);
            ListNode h2 = sortList(p2);
            ListNode sentinel = new ListNode(-1);
            ListNode cur = sentinel;
            while (h1 != null && h2 != null) {
                if (h1.val < h2.val) {
                    cur.next = h1;
                    h1 = h1.next;
                } else {
                    cur.next = h2;
                    h2 = h2.next;
                }
                cur = cur.next;
            }
            if (h1 != null) cur.next = h1;
            if (h2 != null) cur.next = h2;
            return sentinel.next;
        }
    }
}
